package gold.digger;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC726 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public String countOfAtoms(String formula) {
            Map<String, Integer> resMap = countOfAtomsRecur(formula, 0, formula.length() - 1);
            StringBuilder sb = new StringBuilder();
            for (String ele : resMap.keySet()) {
                if (resMap.get(ele).intValue() == 1) sb.append(ele);
                else sb.append(ele).append(resMap.get(ele));
            }

            return sb.toString();
        }

        public Map<String, Integer> countOfAtomsRecur(String formula, int start, int end) {
            Map<String, Integer> elementMap = new TreeMap<>();
            if (start > end) return elementMap;

            for (int i = start; i <= end; ) {
                char cur = formula.charAt(i);
                if (cur <= 'Z' && cur >= 'A') {
                    int elementPos = i + 1;
                    while (elementPos <= end && formula.charAt(elementPos) <= 'z' && formula.charAt(elementPos) >= 'a')
                        ++elementPos;
                    String curElement = formula.substring(i, elementPos);
                    int countPos = elementPos;
                    while (countPos <= end && formula.charAt(countPos) <= '9' && formula.charAt(countPos) >= '0') {
                        ++countPos;
                        if (countPos > end) break;
                    }
                    if (countPos == elementPos) elementMap.put(curElement, elementMap.getOrDefault(curElement, 0) + 1);
                    else {
                        int count = Integer.parseInt(formula.substring(elementPos, countPos));
                        elementMap.put(curElement, elementMap.getOrDefault(curElement, 0) + count);
                    }
                    i = countPos;
                    continue;
                }

                if (cur == '(') {
                    int partCount = 1, nextPartEnd = i + 1;
                    while (partCount > 0) {
                        if (formula.charAt(nextPartEnd) == '(') ++partCount;
                        if (formula.charAt(nextPartEnd) == ')') --partCount;
                        ++nextPartEnd;
                        if (nextPartEnd > end) break;
                    }

                    int countPos = nextPartEnd;
                    while (countPos <= end && formula.charAt(countPos) <= '9' && formula.charAt(countPos) >= '0') {
                        ++countPos;
                        if (countPos > end) break;
                    }
                    int count = countPos == nextPartEnd ? 1 : Integer.parseInt(formula.substring(nextPartEnd, countPos));
                    Map<String, Integer> subCountEleMap = countOfAtomsRecur(formula, i + 1, nextPartEnd - 2);
                    for (String eleKey : subCountEleMap.keySet()) {
                        elementMap.put(eleKey, elementMap.getOrDefault(eleKey, 0) + count * subCountEleMap.get(eleKey));
                    }
                    i = nextPartEnd;
                    continue;
                }
                ++i;
            }

            return elementMap;
        }
    }

    class Solution_Other_Success {
        public String countOfAtoms(String formula) {
            //记录（ 以元素计算的索引  CaHO(  此时 ( 的索引为 3
            LinkedList<Integer> recordFrontBracket = new LinkedList<>();

            int len = formula.length();
            //记录元素名CaHO    Ca → H → O
            ArrayList<String> atoms = new ArrayList<>(len);
            //记录atoms对应索引元素的个数CaHO   1 → 1 → 1
            ArrayList<Integer> counts = new ArrayList<>(len);
            for (int i = 0; i < len; i++) {
                char c = formula.charAt(i);
                if (c == '(') {
                    //记录（ 的索引
                    recordFrontBracket.add(atoms.size());
                } else if (c == ')') {
                    //获取 `()` 后的数字
                    int number = 0;
                    while (i + 1 < len && isDigital(formula.charAt(i + 1))) {
                        number = number * 10 + formula.charAt(i + 1) - '0';
                        i++;
                    }
                    if (number == 0) {
                        //没有 默认为 1
                        number = 1;
                    }
                    //得到和 `)` 匹配的 `(` 的索引
                    int index = recordFrontBracket.removeLast();
                    //然后给 counts 中 索引从 index开始到最后的 元素对应的个数 乘以 number
                    for (int j = index; j < counts.size(); j++) {
                        counts.set(j, counts.get(j) * number);
                    }
                } else if (isUpperCase(c)) {
                    //获取元素名
                    int t = i;
                    while (t + 1 < len && isLowerCase(formula.charAt(t + 1))) {
                        t++;
                    }
                    //添加到存元素的列表
                    atoms.add(formula.substring(i, t + 1));
                    i = t;
                    //计算此时 元素后面的数字
                    int count = 0;
                    while (i + 1 < len && isDigital(formula.charAt(i + 1))) {
                        count = count * 10 + formula.charAt(i + 1) - '0';
                        i++;
                    }
                    if (count == 0) {
                        //没有 默认为 1
                        count = 1;
                    }
                    //添加到存元素数量的列表
                    counts.add(count);
                }
            }
            //统计 所有元素 以及 其总数量
            Map<String, Integer> map = new HashMap<>();
            for (int i = 0; i < atoms.size(); i++) {
                map.put(atoms.get(i), map.getOrDefault(atoms.get(i), 0) + counts.get(i));
            }
            //获取所有元素名
            String[] arr = new String[map.size()];
            Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
            int index = 0;
            while (iterator.hasNext()) {
                arr[index] = iterator.next().getKey();
                index++;
            }
            //并对其按字母排序
            Arrays.sort(arr);
            StringBuilder res = new StringBuilder();
            for (int i = 0; i < arr.length; i++) {
                //添加元素
                res.append(arr[i]);
                //添加对应的数量  1的话不添加
                int count = map.get(arr[i]);
                res.append(count != 1 ? count : "");
            }
            return res.toString();
        }

        public boolean isDigital(char c) {
            return c >= '0' && c <= '9';
        }

        public boolean isUpperCase(char c) {
            return c >= 'A' && c <= 'Z';
        }

        public boolean isLowerCase(char c) {
            return c >= 'a' && c <= 'z';
        }
    }


    //formula = "K4(ON(SO3)2)2"
//Output: "K4N2O14S4"
//Explanation:
//The count of elements are {'K': 4, 'N': 2, 'O': 14, 'S': 4}.
    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.countOfAtoms("K4(ON(SO3)2)2"));
    }

    public static void main(String[] args) throws Exception {
        LC726 an = new LC726();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}